package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-05 20:11
 */
public class n_53 {
    public static void main(String[] args) {
        n_53 n = new n_53();
        int[] arr={1,2,3,3,3,3,4,5};
        int res = n.GetNumberOfK(new int[]{3}, 3);
        System.out.println(res);
    }


    /**
     * 我的写法-不太行啊
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK(int [] array , int k) {
        int left =0;
        int right = array.length-1;
        int count=0;
        while (left<=right){
            int mid = left+(right-left)/2;
            if (array[mid]==k){
                count++;
                //mid往前找和往后找
                for (int i = 1; mid-i>=left; i++) {
                    if(array[mid-i]==k){
                        count++;
                    }
                }
                for (int i = 1; mid+i <=right; i++) {
                    if (array[mid+i]==k){
                        count++;
                    }
                }
                break;
            }else if (array[mid]<k){
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return count;
    }

    /**
     * 思路：
     * 下界定义为：如果存在目标值，则指向第一个目标值，否则，如果不存在， 则指向大于目标值的第一个值。
     * 上界定义为：不管目标值存在与否，都指向大于目标值的第一个值。
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK2(int [] array , int k) {
        int lbound=0,rbound=0;
        int l =0,r=array.length;
        //下界
        while (l<r){
            int mid =l+(r-l)/2;
            if (array[mid]>=k){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        lbound=l;
        //上界
        l=0;
        r=array.length;
        while (l<r){
            int mid =l+(r-l)/2;
            if (array[mid]<=k){
                l=mid+1;
            }else {
                r=mid;
            }
        }
        rbound=l;
        return rbound-lbound;
    }

    /**
     * 思想类似上面，但更好理解的：
     * 下界：第一个的前面
     * 上界：最后一个
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK3(int [] array , int k) {
        int l=0,r=array.length-1,mid;
        while (l<=r){
            mid=l+(r-l)/2;
            if (array[mid]>=k){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        int lbound=l;
        l=0;r=array.length-1;
        while (l<=r){
            mid=l+(r-l)/2;
            if (array[mid]>k){
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        int rbound=l;
        return rbound-lbound;
    }
}
